﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0031_Search : IAlgorithm
    {
        // 704. 二分查找

        // 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

        // 提示：
        //   你可以假设 nums 中的所有元素是不重复的。
        //   n 将在[1, 10000]之间。
        //   nums 的每个元素都将在[-9999, 9999]之间。

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { -1, 0, 3, 5, 9, 12 };
            int target = 2;
            // 算法执行与打印
            Console.WriteLine(Search(nums, target));
        }

        // 算法
        public int Search(int[] nums, int target)
        {
            int s = 0, e = nums.Length - 1;
            while (s <= e)
            {
                // m有坑 不能两个除2
                var m = (e - s) / 2 + s;
                if (nums[m] == target)
                    return m;
                else if (nums[m] > target)
                    e = m - 1;
                else
                    s = m + 1;
            }
            return -1;
        }
        public int Search1(int[] nums, int target)
        {
            int low = 0, high = nums.Length - 1;
            while (low <= high)
            {
                int mid = (high - low) / 2 + low;
                int num = nums[mid];
                if (num == target)
                    return mid;
                else if (num > target)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            return -1;
        }
    }
}
